from typing import List


class PermuteUnique47:
    """
    47. 全排列 II
        给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
        示例 1：
        输入：nums = [1,1,2]
        输出：
        [[1,1,2],
         [1,2,1],
         [2,1,1]]
        示例 2：
        输入：nums = [1,2,3]
        输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

        提示：
        1 <= nums.length <= 8
        -10 <= nums[i] <= 10
    """
    def permute_unique(self, nums: List[int]) -> List[List[int]]:
        res = []
        temp = []
        flg = [False * len(nums) for _ in range(len(nums))]
        self.find_resu(nums, res, flg, temp, 0)
        return res

    def find_resu(self, nums: List[int], res: List[List[int]], flg: List[bool], temp: List[int], index: int):
        if len(nums) == index:
            res.append([temp[0:]])

        for i in range(len(nums)):
            if flg[i] or (i > 0 and nums[i] == nums[i - 1] and not flg[i - 1]):
                continue
            temp.append(nums[i])
            flg[i] = True
            self.find_resu(nums, res, flg, temp, index + 1)
            del temp[index]
            flg[i] = False
